package kyssion.leetcode.num201_250;

public class code201_数字范围按位与 {
    public static void main(String[] args) {
        System.out.println(new code201_数字范围按位与().rangeBitwiseAnd(2,
                6));
    }

    public int rangeBitwiseAnd(int m, int n) {
        int oldn = n;
        int oldm = m;
        int item = 0;
        int index = 1;
        int next = 0;
        while (m != 0) {
            int i = m & 1;
            int j = n & 1;
            if (i != 0 && j != 0) {
                int base = next | oldm;
                if (base >= oldn) {
                    item += index;
                }
            }
            next = (next << 1) + 1;
            index = index << 1;
            m = m >> 1;
            n = n >> 1;
        }
        return item;
    }

    /**
     * 玄学
     *
     * @param m
     * @param n
     * @return
     */
    public int rangeBitwiseAnd2(int m, int n) {
        while (m < n) {
            n = n & (n - 1);
        }
        return n;
    }

    /**
     * n的二进制位比m二进制最左边的1高时，&的结果必然为0；
     * 由这个思想启发，二进制最高位相同时，这个1会保存，然后比较右一位，相同也保留...
     * 所以只需要m n 同时右移到相等时 m n的值就是&后能保留的位数，然后左移回来就是最后的值。
     */
    int rangeBitwiseAnd3(int m, int n) {
        int count = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            count++;
        }
        return m << count;
    }
}
